package com.ztom.top100;

/**
 * 回文子串
 * <p>
 * https://leetcode-cn.com/problems/palindromic-substrings/
 *
 * @author ZhangTao
 */
public class Code99CountSubstrings {

    /**
     * manacher  每个位置上最长回文半径
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int res = 0;
        char[] chars = manacherStr(s);
        int[] pArr = new int[chars.length];
        int r = -1;
        int c = -1;
        for (int i = 0; i < chars.length; i++) {
            pArr[i] = i <= r ? Math.min(pArr[2 * c - i], r - i + 1) : 1;
            while (i + pArr[i] < chars.length && i - pArr[i] >= 0) {
                if (chars[i + pArr[i]] == chars[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }

            if (i + pArr[i] - 1 > r) {
                r = i + pArr[i] - 1;
                c = i;
            }

            res += pArr[i] / 2;
        }
        return res;
    }

    private char[] manacherStr(String s) {
        char[] chars = s.toCharArray();
        char[] res = new char[2 * chars.length + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : chars[i / 2];
        }
        return res;
    }
}
